
//1524.和为奇数的子数组数目
class Solution {
    #define MOD 1000000007
public:
    int numOfSubarrays(vector<int>& arr) {
        //奇数 - 偶数 = 奇数 , 偶数 - 奇数 =奇数
        //所以对每个前缀和,在前面找有多少个奇数或偶数的数组即可

        int n = arr.size();
        unordered_map<int,int> m;   //存储每个前缀和的值以及个数
        m[0] = 1 ,m[1] = 0;         //用0和1表示奇偶,偶数置为1是因为一开始哈希表中就有一个0

        int sum = 0 , ret = 0;
        for(int i = 0; i < n ; i++)
        {
            sum = (sum + arr[i])%2;
            ret = (ret + (sum%2==0?m[1]:m[0]))%MOD;
            m[sum%2] = (m[sum%2]+1)%MOD;
        }
        return ret;
    }
};